package com.ys.sort;

/**
 * @author CodeYang
 * @Description TODO
 * @Date 2020/12/11 11:57
 */
public class 二分查找 {

    public static void main(String[] args) {
        int[] arr = {2, 4, 5, 6, 7, 9, 10};
        System.out.println(binarySearch(arr,5));
    }

    /**
     * 二分查找: 查询指定元素
     * 特点: 效率高
     * 前提: 要求数组元素必须有序
     * 也称游标查找法:
     * 如果目标 在 数组中存在满足:
     * 1 定义 首尾游标 min =0 ,max = arr.length -1 如果 元素能取到的区间范围[min,max]
     * 2: 每次进入 循环比对 都定义一个 mid = (min+max)/2
     * (这里循环的次数是不明确的,所以需要用到死循环)
     * a> 如果 目标元素 > arr[mid] ,则证明目标元素在 mid的右侧,更新mid =mid+1
     * b> 如果 目标元素 < arr[mid] ,则证明目标元素在mid的左侧,更新ma= max -1
     * c> 如果 目标元素==arr[mid],则证明 查找到了,目标元素的索引值就是mid
     * 3: 如果 mid> max ,则证明查找元素正在数组中不存在
     *
     * @param arr           查找数组
     * @param targetElement 目标元素
     * @return
     */
    static int binarySearch(int arr[], int targetElement) {
        // 1定义游标
        int min = 0, max = arr.length - 1;
        while (true) {
            int mid = (min + max) / 2;
            if (targetElement > arr[mid]) {
                // 在右侧
                min = min + 1;
            } else if (targetElement < arr[mid]) {
                //在左侧
                max = max - 1;
            } else {
                // traget == arr[mid] 索引找到
                return mid;
            }
            // 没找到
            if (min > max) {
                return -1;
            }
        }

    }
}
